package cn.fxzhang.leetcode.no00;

import java.util.HashMap;

/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 类型：字符串处理
 * 题解：根据子串有序性的特点，当出现重复字符时，更新子串的起始位置
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/2)：
 * 执行用时: 7 ms, 击败了79.41%%
 * 内存消耗: 38.6 MB, 击败了53.45%
 *
 * 【中等】通过次数917,362提交次数2,491,971
 * @author 张晓帆
 * @date 2021/4/2
 */
public class P0003_Longest_Substring_Without_Repeating_Characters {

    public int lengthOfLongestSubstring(String s) {
        // 记录每个字符出现的最新位置
        HashMap<Character, Integer> location = new HashMap<>();
        // 子串起始位置
        int k = 0;
        int max = 0;
        for (int i=0; i< s.length(); i++){
            Integer loc = location.get(s.charAt(i));
            // 出现重复字符串时，更新位置
            if (loc != null && loc >= k) {
                k = loc + 1;
            }
            location.put(s.charAt(i), i);
            max = Math.max(max, i-k+1);
        }
        return max;
    }
}
